package stack.Leetcode;

import java.util.Stack;

/**
 * 碰到左括号直接入栈，碰到右括号出栈，查看是否匹配
 * 当扫描完整个字符串后仍然没有找到反例，并且当前栈为空，就满足条件
 */
public class Num20 {

    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        //将字符串转为单个字符
        for (int i = 0; i < s.length(); i++) {
             char c=s.charAt(i);
             if (c == '('||c == '{'||c == '['){
                 //此时c是左括号，入栈
                 stack.push(c);
             }else {
                 //此时碰到了右括号，弹出栈顶元素并且查看是否匹配
                 //str=>'}])'时
                 if (stack.isEmpty()){
                     //肯定是先有左括号，如果第一个字符就是右括号，就一定是false
                     return false;
                 }
                 char top=stack.pop();
                 //找反例
                 if (c==')'&& top!='（'){
                     return false;
                 }
                 if (c==']'&& top!='['){
                     return false;
                 }
                 if (c=='}'&& top!='{'){
                     return false;
                 }
             }
        }
        //当匹配结束后，此时栈不为空，就是左括号数大于右括号数的情况
        return stack.isEmpty();
    }
}
